def bubble_sort(arr):
    """
    冒泡排序算法实现
    
    参数:
        arr: 需要排序的列表
    
    返回:
        排序后的列表
    """
    n = len(arr)
    
    # 外层循环控制排序轮数
    for i in range(n):
        # 标记是否发生交换，用于优化
        swapped = False
        
        # 内层循环进行相邻元素比较和交换
        for j in range(0, n - i - 1):
            # 如果前一个元素大于后一个元素，则交换
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 如果这一轮没有发生交换，说明数组已经有序
        if not swapped:
            break
    
    return arr


def bubble_sort_with_steps(arr):
    """
    带步骤显示的冒泡排序算法
    
    参数:
        arr: 需要排序的列表
    
    返回:
        排序后的列表
    """
    n = len(arr)
    print(f"原始数组: {arr}")
    
    for i in range(n):
        swapped = False
        print(f"\n第 {i + 1} 轮排序:")
        
        for j in range(0, n - i - 1):
            print(f"  比较 {arr[j]} 和 {arr[j + 1]}", end="")
            
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                print(f" -> 交换: {arr}")
            else:
                print(f" -> 不交换: {arr}")
        
        if not swapped:
            print("  数组已有序，提前结束")
            break
    
    return arr


if __name__ == "__main__":
    # 测试用例
    test_arrays = [
        [64, 34, 25, 12, 22, 11, 90],
        [5, 2, 8, 1, 9],
        [1, 2, 3, 4, 5],  # 已排序
        [5, 4, 3, 2, 1],  # 逆序
        [1],              # 单个元素
        []                # 空数组
    ]
    
    print("=== 冒泡排序测试 ===\n")
    
    for i, arr in enumerate(test_arrays, 1):
        print(f"测试用例 {i}:")
        original = arr.copy()
        sorted_arr = bubble_sort(arr.copy())
        print(f"原始: {original}")
        print(f"排序后: {sorted_arr}")
        print("-" * 40)
    
    print("\n=== 带步骤的冒泡排序演示 ===")
    demo_array = [64, 34, 25, 12, 22, 11, 90]
    bubble_sort_with_steps(demo_array.copy())
